package dynamtic;

import java.util.Arrays;

/**
 * 给你 k种面值的硬币，面值分别为 c1, c2 ... ck，每种硬币的数量无限，
 * 再给一个总金额amount，问你最少需要几枚硬币凑出这个金额，如果不可
 * 能凑出，算法返回 -1 。算法的函数签名如下：
 * coins 中是可选硬币面值，amount 是目标金额
 * int coinChange(int[] coins, int amount);
 *
 * @Auther Jun jie Yi
 * @Date 20:05 2022/2/10
 */
public class GetMoney {

    public static void main(String[] args) {
        int[] coins = {1, 2, 5};
        int amount = 11;
        coinChange(coins, amount);
    }

    //定义备忘录数组
    static int[] memo;

    static int coinChange(int[] coins, int amount) {
        memo = new int[amount + 1];
        Arrays.fill(memo, Integer.MAX_VALUE);
        System.out.println(dp3(coins, amount));
        return 0;
    }

    //1.暴力递归解法
    static int dp1(int[] coins, int n) {
        if (n == 0) return 0;//刚好讲钱数凑齐
        if (n < 0) return -1;
        //求最小值，所以初始化为正无穷
        int min = Integer.MAX_VALUE;
        for (int coin : coins) {
            int t = dp1(coins, n - coin);
            if (t == -1) continue;//-1是凑不起钱的无用
            min = Math.min(min, t + 1);
        }
        System.out.println("钱数：" + n);
        System.out.println("硬币数：" + min);
        return min;
    }

    //2.添加备忘录
    static int dp2(int[] coins, int n) {
        if (n == 0) return 0;
        if (n < 0) return -1;
        // 查备忘录，防止重复计算
        if (memo[n] != Integer.MAX_VALUE) {
            return memo[n];
        }
        //求最小值，所以初始化为正无穷
        int min = Integer.MAX_VALUE;
        for (int coin : coins) {
            int t = dp2(coins, n - coin);
            if (t == -1) continue;
            min = Math.min(min, t + 1);
        }
        memo[n] = (min == Integer.MAX_VALUE) ? -1 : min;

        System.out.println("钱数：" + n);
        System.out.println("硬币数：" + min);
        return min;
    }

    //3.dp数组动态规划解法
    static int dp3(int[] coins, int n) {
        int[] dp = new int[n + 1];
        Arrays.fill(dp, n + 1);
        dp[0] = 0;
        for (int i = 0; i < dp.length; i++) {
            for (int coin : coins) {
                if (i - coin >= 0) {
                    dp[i] = Math.min(dp[i], dp[i - coin] + 1);
                }
            }
        }
        System.out.println(Arrays.toString(dp));
        return dp[n] == n + 1 ? -1 : dp[n];
    }

}
